package com.LeeCode;

import java.util.Arrays;

/**
 * 满足条件的子序列数目
 */

public class Code1498 {
    public static void main(String[] args) {
        int[] nums = {6, 10, 12, 3, 29, 21, 12, 25, 17, 19, 16, 1, 2, 24, 9, 17, 25, 22, 12, 22, 26, 24, 24, 11, 3, 7, 24, 5, 15, 30, 23, 5, 20, 10, 19, 20, 9, 27, 11, 4, 23, 4, 4, 12, 22, 27, 16, 11, 26, 10, 23, 26, 16, 21, 24, 21, 17, 13, 21, 9, 16, 17, 27};
        int target = 26;
        System.out.println(new Code1498().numSubseq(nums, target));

    }

    private static final int MOD = 1_000_000_007;
    private static final int[] pow2 = new int[100_000]; // 2^i
    private static boolean initialized = false;

    // 这样写比 static block 快
    private void init() {
        if (initialized) {
            return;
        }
        initialized = true;

        pow2[0] = 1;
        for (int i = 1; i < pow2.length; i++) {
            pow2[i] = pow2[i - 1] * 2 % MOD;
        }
    }

    public int numSubseq(int[] nums, int target) {
        init();
        Arrays.sort(nums);
        long ans = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) { // 可以相等，此时子序列的最小最大是同一个数
            if (nums[left] + nums[right] <= target) {
                // nums[left] 可以作为子序列的最小值
                // 其余下标在 [left+1,right] 中的数选或不选都可以
                ans += pow2[right - left];
                left++;
            } else {
                // nums[right] 太大了，即使与剩余元素的最小值 nums[left] 相加也不满足要求
                right--;
            }
        }
        return (int) (ans % MOD);
    }
}
